public class BinarySearchTree {

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }

    public TreeNode root=null;

    public TreeNode search(int key){
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val<key){
                cur=cur.right;
            }else if(cur.val> key){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        return null;
    }

    //插入
    public void insert(int val){
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
            return;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }else{
                return;
            }
        }
        //此时,parent 就是要插入节点的 父亲节点
        if(parent.val <val){
            parent.right=node;
        }else{
            parent.left=node;
        }
    }

    //删除
    public void remove(int key){
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(key>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(key<cur.val){
                parent=cur;
                cur=cur.left;
            }else{//前面两步 找到要删的节点cur和其父节点parent,最后用删除节点方法 删除
                removeNode(parent,cur);
                return;
            }
        }
    }

    public void removeNode(TreeNode parent,TreeNode cur){
        if(cur.left == null){
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if(cur.right == null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{
            //用cur的右树 的 最小值(一直找到左树的底)
            TreeNode target=cur.right;
            TreeNode targetP=cur;
            while(target.left!=null){
                targetP= target;
                target=target.left;
            }
            cur.val=target.val;//t的值替换了cur的值,即 删除
            if(target==targetP.left){
                targetP.left=target.right;
            }else{
                targetP.right=target.right;
            }

        }
    }
}
